package com.javabasic.algorithm.sword_of_offer;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Queue;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/1/12 10:09 下午
 */
public class 剑指_Offer_32_III_从上到下打印二叉树_III {

    /**
     * BFS + 步长记录 + MAP
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        if (root == null) {
            return result;
        }

        Queue<NewTreeNode> queue = new LinkedList<>();
        NewTreeNode currentNode = new NewTreeNode(root, 0), tempNode;
        queue.offer(currentNode);
        int deep, newDeep;
        TreeNode temp;
        List<TreeNode> nodeList;
        Map<Integer, List<TreeNode>> indexToList = new HashMap<>(16);

        while (!queue.isEmpty()) {

            currentNode = queue.poll();
            deep = currentNode.deep;
            temp = currentNode.node;

            nodeList = indexToList.getOrDefault(deep, new ArrayList<>());
            nodeList.add(temp);
            indexToList.put(deep,nodeList);

            newDeep = deep + 1;
            if (temp.left != null) {
                tempNode = new NewTreeNode(temp.left, newDeep);
                queue.offer(tempNode);
            }
            if (temp.right != null) {
                tempNode = new NewTreeNode(temp.right, newDeep);
                queue.offer(tempNode);
            }
        }
        int len = indexToList.size(), val;
        List<TreeNode> treeNodes;
        List<Integer> nums;
        for (int i = 0; i < len; i++) {
            treeNodes = indexToList.get(i);
            if (!treeNodes.isEmpty()) {
                nums = new ArrayList<>();
                if ((i&1) == 1) {
                    Collections.reverse(treeNodes);
                    for (TreeNode treeNode : treeNodes) {
                        val = treeNode.val;
                        nums.add(val);
                    }
                } else {
                    for (TreeNode treeNode : treeNodes) {
                        val = treeNode.val;
                        nums.add(val);
                    }
                }
                result.add(nums);
            }
        }
        return result;
    }

    class NewTreeNode {
        TreeNode node;
        int deep;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            NewTreeNode that = (NewTreeNode) o;
            return deep == that.deep && Objects.equals(node, that.node);
        }

        @Override
        public int hashCode() {
            return Objects.hash(node, deep);
        }

        public TreeNode getNode() {
            return node;
        }

        public void setNode(TreeNode node) {
            this.node = node;
        }

        public int getDeep() {
            return deep;
        }

        public void setDeep(int deep) {
            this.deep = deep;
        }

        public NewTreeNode(TreeNode node, int deep) {
            this.node = node;
            this.deep = deep;
        }
    }
}
